package lib

import "algorithms/ds"

func init() {
	Probs = append(Probs, Problem{
		Num:         437,
		Discription: "二叉树指定路径和的路径个数（只能从上到下）",
		Level:       2,
		Labels: map[string]int{
			"递归": 1,
			"回溯": 1,
		},
	})
}

//每个节点都当路径的起始点算一遍
func PathSum2(root *ds.TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}

	return rootSum(root, targetSum) + PathSum2(root.Left, targetSum) + PathSum2(root.Right, targetSum)
}

//以该根节点为起始的路径中，满足路径和的路劲数
func rootSum(root *ds.TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}

	count := 0
	if root.Val == targetSum {
		count++
	}

	count += rootSum(root.Left, targetSum-root.Val)
	count += rootSum(root.Right, targetSum-root.Val)
	return count
}
